---
title: "L2-008 最长对称子串"
created: 2025-11-28
tags:
  - 算法
---

# L2-008 最长对称子串

## 题目 [L2-008 最长对称子串](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805067704549376&page=1)

![[image-41100f18.png]]

## 思路分析

回文串分为两种 一种是以奇数长度的以中间位置为中心 一种是以偶数长度的以间隙为中心

考虑清楚这两种情况 分别传入i,i  和 i,i+1 到中心拓展算法中

所谓中心拓展算法 其实就是双指针暴力

遍历每个点 以它为个中心 向左向右拓展 找到最长的回文串坐标

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

PII findLongest(const string& s,int l, int r){

	while(l>=0 && r<=s.size() && s[l]==s[r]){

		l--;

		r++;

	}

	return {l+1,r-1};

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	string s;getline(cin,s);

	int start=0,end=0;

	for(int i=0;i<s.size();i++){

		auto odd = findLongest(s,i,i);

		int left1=odd.first,right1=odd.second;

		auto even = findLongest(s,i,i+1);

		int left2=even.first,right2=even.second;

		if(right1-left1 > end-start){

			start=left1;

			end=right1;

		}

		if(right2-left2 > end-start){

			start=left2;

			end=right2;

		}

	}

	cout<<end-start+1;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-007 家庭房产|L2-007 家庭房产]] 🏠 [[00-天梯赛]] ➡️ [[L2-009 抢红包|L2-009 抢红包]]